/*
 * @lc app=leetcode.cn id=481 lang=cpp
 *
 * [481] 神奇字符串
 */

// @lc code=start
class Solution {
public:
    int magicalString(int n) {
        if (n < 4) return 1;
        int *s = new int[n];
        for (int i = 0; i < n; i++) {
            if (i == 0)
                s[0] = 1;
            else if (i == 1 || i == 2)
                s[i] = 2;
            else
                s[i] = 0;
        }
        int ans = 1, i = 2, j = 3;
        while (j < n) {
            int size = s[i], num = 3 - s[j - 1];
            while (size && j < n) {
                if (num == 1) ans++;
                s[j++] = num;
                size--;
            }
            i++;
        }
        delete[] s;
        return ans;
    }
};
// @lc code=end
